#include<iostream>

using namespace std;
const int N=1e7+10;
bool st[N];
int phi[N],p[N],cnt;
typedef long long ll;
void get_phi()
{
	phi[1]=1;
	for(int i=2;i<=N;i++)
	{
		if(!st[i])
		{
			p[cnt++]=i;
			phi[i]=i-1;
		}

		for(int j=0;1ll*p[j]*i<=N;j++)
		{
			int x=p[i]*i;
			st[x]=true;
			if(i%p[j]==0)
			{
				phi[x]=p[j]*phi[i];
				break;
			}
			else
			{
				phi[x]=(p[j]-1)*phi[i];
			}
		}
	}
}

ll qpow(ll a,ll b,ll c)
{
	ll ret=1;
	while(b)
	{
		if(b&1) ret=ret*a%c;
		b>>=1;
		a=a*a%c;
	}

	return ret;
}

int dfs(int p)
{
	if(p==1) return 0;
	return qpow(2,dfs(phi[p])+phi[p],p);
}

int main()
{
	get_phi();

	int t;cin>>t;

	while(t--)
	{
		int p;cin>>p;
		cout<<dfs(p)<<endl;
	}
}